S3 Group

The S3 group is the group of permutation on 3 elements. It has 6 elements. It is the group of all the automorphism on the set {1, 2, 3}.

Here is the full list of the elements of S3:

## e: ()
## a: (1,2)
## b: (1,3)
## c: (2,3)
## p: (1,2,3)
## p^2: (1,3,2)

Table of S3:

S3 e p p2 a b c
e e p p2 a b c
p p p2 e c a b
p2 p2 e p b c a
a a b c e p p2
b b c a p2 e p
c c a b p p2 e

Order of the elements:

S3 Order Sign Inversions
e 1 + 0
p 3 + 0
p2 3 + 0
a 2 - 1
b 2 - 1
c 2 - 1

Unique normal chain decomposition of S3:

\[ C(2) \lhd C(3) \lhd S_3\]

And this decomposition is unique, the factors cannot be swapped.

Cycle graph

grViz('
graph cycle {
 graph[layout = neato]
 node [shape = circle, style = filled, color = grey, label=""]

 e [color = red]; a; b; c; p; p2

  e -- a
  e -- b
  e -- c
  e -- p -- p2 -- e
}
')

Subgroups of S3

<p> is a normal subgroup

The group <p> = {e, p, p2} is normal in S3:

all(p^a == p2, p^b == p2, p^c == p2)
## [1] TRUE

The classes of <p> in S3 are:

{e, p, p2}, {a, b, c}

The action of a on <p>: (p p2)

More detailed action of the group on <p>:

S3 {e, p, p2} {a, b, c}
e {e, p, p2} {a, b, c}
a {a, b, c} {e, p, p2}
b {b, c, a} {p2, e, p}
c {c, a, b} {p, p2, e}
p {p, p2, e} {c, a, b}
p2 {p2, e, p} {b, c, a}

<p> is isomorphic to Z/3Z and it has no non-trivial subgroups.

If G is a subgroup of S3 containing <p> then G*<p> is a subgroup of S3/<p>. S3/<p> is a group of order 2 so it is isomorphic to Z/2Z and it has no non trivial subgroup. The only subgroups containing p are {e} and S3.

If G is a sub-group not including <p>. Then inter(G, <p>) is {e}. because inter(G, <p>) is a subgroup of <p> and it cannot be <p> because G does no include <p>.

So G is included in {e, a, b, c}. G cannot contain more than 2 elements because any of products ab, bc, … will yield an element of <p>. So G is either {e, a}, {e, b}, {e, c}.

Conclusion: Here is the full list of the subgroups of S3: {e}, {e, a}, {e, b}, {e, c}, {e, p, p2}, {e, a, b, c, p, p2}

Lattice of all the subgroups

## Warning in .Call("R_igraph_layout_fruchterman_reingold", graph, coords, :
## '.Random.seed' is not an integer vector but of type 'NULL', so ignored

Normal subgroups

Actions of the group

The natural action of S3 on {1, 2, 3}

This is a faithful action.

We can compute the orbits:

S3 Orbits
e {1} {2} {3}
a {1, 2} {3}
b {1, 3} {2}
c {1} {2, 3}
p {1, 2, 3}
p2 {1, 2, 3}

We can also compute the stabilizers:

{1, 2, 3} Stabilizer
1 <c>
2 <b>
3 <a>

Action on the ‘edges’

We consider the action of S3 on this set: {{1, 2}, {1, 3}, {2, 3}}

  • Action of <p>
## [1] TRUE
  • Action of a:
all(
  a_f(c(1, 2)) == c(2, 1),
  a_f(c(1,3)) == c(2, 3),
  a_f(c(2, 3)) == c(1, 3))
## [1] TRUE

Since a and p generate S3 we deduce that the action is faithfull.

Orbits

S3 Orbits
e {1_2} {1_3} {2_3}
a {1_2} {1_3, 2_3}
b {1_2, 2_3} {1_3}
c {1_2, 1_3} {2, 3}
p {1_2, 2_3, 1_3}
p2 {1_2, 2_3, 1_3}

Stabilizers

Action on the elements of order 2

The elements of order 2 are: a, b, c

c(a^p == c, a^(p^2) == b)
## [1] TRUE TRUE

So the action is transitive. And |O(a)|.|Stab(a)| = 6 => 3.|Stab| = 6 So the stabilizer size is 2.

And:

S3 Stab
a e, a
b e, b
c e, c

Action on the elements of order 3

The elements of order 3 are: p, p^2

c(p^a == p^2)
## [1] TRUE

So the action is transitive and: |O(p)|.|Stab(p)| = 6 so |Stab(p)| = 2

S3 Stab
p e, p, p2
p2 e, p, p2

Beat actions

Let f be a recording, and p a permutation of the indices of the recording. f’ is the image of f by p if the index 2 of f’ is the index i of f such that p(i) = 2. So \(i = p^{-1}(2)\)

Let’s write a function that applies a permutation to a recording.

apprec <- function(gp) {
  function(...) {
    f <- c(...)
    f[as.word(gp) %>% unclass %>% c]
  }
}

Definition

S3 has an action on

Beat 1 2 3 4 5 6
1 x x x x x x
2 x x x x x x
p.1 1 2 3 4 5 6
p.2 3 1 2 6 4 5
a.1 4 5 6 1 2 3
a.2 1 2 3 4 6 5
p2.2 2 3 1 5 6 4
apa.2 3 1 2 5 6 4

This convention means that the action of p.2 is given by 1 -> 3, 2 -> 1, 3 -> 2… And \((p \bullet f)_i = f_{p(i)}\) So that (pf)(1) = f(2). So it we want to know where the value at index 1 is sent we need to find where is the 1 on the p line. So here it is at index 2. That means the value at 1 is taken to index 2. e.g pf(2) = f(1). So that’s how to read this.

However this is not an action because:

\((g h \bullet f)_i = f_{gh(i)} = f_{h(g(i))} = (h \bullet g \bullet f)_i\) so \(g h \bullet f = h \bullet g \bullet f\)

However we have

\(f \bullet g h = f_{gh(i)} = f_{h(g(i))} = (f \bullet g \bullet h)_i\) so \(f \bullet g h = f \bullet g \bullet h\)

So it is a ‘contra-action’ and it is given by a morphism \(\phi: S3 \rightarrow S(Rec)^{op}\) Actually \(\phi\) is a composition: \(S3 \rightarrow S(S3) \rightarrow S(Rec)\) Where the first morphism is contravariant and the second one is covariant. So the composition is a contravariant morphism.

The action of p on the first layer is the trivial one. The action of a on the first layer just switches 2 the 2 3-blocks.

The action of p on the second layer circulates the 2 3-blocks. It has 2 orbits. The action of a on the second layer first 3-block is the trivial one. On the second 3-block it switches 5 and 6.

In order to define the action we remember this following presentation of S3: \(<a^2, p^3, apa = p^2>\)

Check that the action on the first row is an action: \(\phi_1(a) = (1 4) (2 5) (3 6)\) \(\phi_1(p) = id\)

The images verify all the relations, so it is indeed an action.

Check that the action on the second row is an action: \(\phi_2(a) = (5 6)\) \(\phi_2(p) = (1 2 3) (4 5 6)\)

gp <- as.cycle(1:3) * as.cycle(4:6)
ga <- as.cycle(5:6)

So apparently this is not an action since gp^ga != gp^2

gp^ga == gp^2
## [1] FALSE

We can try this one:

Beat 1 2 3 4 5 6
a.2 4 5 6 1 3 2

We have for the second row:

ga <- as.word(c(4, 5, 6, 1, 3, 2))

This also doesn’t work since ga^2 is not identity.

What about this one?

Beat 1 2 3 4 5 6
p.2 2 3 1 5 6 4
a.2 4 6 5 1 3 2 
ga <- as.word(c(4, 6, 5, 1, 3, 2))
cat('ga: ', as.character(as.cycle(ga)), '\r\n')
## ga:  (1,4)(2,6)(3,5) 
cat('gp: ', as.character(as.cycle(gp)))
## gp:  (1,2,3)(4,5,6)

We have:

c(gp^3 == as.cycle(), 
  ga^2 == as.cycle(),
  gp^ga == gp^2)
## [1] TRUE TRUE TRUE

So it is an action of S3

Beat 1 2 3 4 5 6
e 1 2 3 4 5 6
a 4 6 5 1 3 2
p 2 3 1 5 6 4
p2 3 1 2 6 4 5
ap 5 4 6 2 1 3
ap2 6 5 4 3 2 1

Automorphism of the action

Let \(\eta: Rec \rightarrow Rec\) where Rec is the set of all recordings of this action. We let \(\eta(f)_i = 1 + f_i\) That is if \(f_i = 1\) then \(\eta(f)_i = 0\) and if \(f_i = 0\) then \(\eta(f)_i = 1\)

We can easily show that \(\eta\) is injective, surjective and it’s inverse is itself.

Furthermore we can show that \(\eta\) is a group action morphism: $(f g)_i = 1 + (f g)i = 1 + f{g(i)} $ and \((\eta(f) \bullet g)_i = \eta(f)_{g(i)} = 1 + f_{g(i)}\)

In particular \(\eta\) is a bijection between beats.

Decomposition into orbits

Assuming each slot can be either 0 or 1 then we have 2^6 = 64 different records.

We can classify the beats by the number of records they contain.

|O|.|Stab| = 6 So the size of the beats is either 1, 2, 3 or 6.

  • Classification of the beats of size 1

Let B be a bit of size 1 and f the only recording inside that beat. Then we have \[p.f = f \implies p.f(1) = f(1) \implies f(2) = f(1)\] Duplicating this with p2, a, ap, ap2 yields respectively f(3) = f(1), f(4) = f(1), f(5) = f(1), f(6) = f(1).

In the end we have shown that f is constant which means f = 0 or f = 1. Both solution works so we have shown that there are exactly 2 beats of size 1.

0 0 0 0 0 0 and
1 1 1 1 1 1

  • Classification of the beats of size 2

Let B be a bit of size 2. We can write B = {f, g}. We have |Stab(f)| = 3 so Stab(f) = {e, p, p2}. And similarly for g.

\(pf = f \textrm{ and } p^2f = f \implies \\f(1) = f(2) = f(3) \textrm{ and } f(4) = f(5) = f(6)\)

So f is of the form (x,x,x,y,y,y). Furthermore we must have \(x \neq y\) because otherwise B would have size 1. So finally f is one of:

0 0 0 1 1 1
1 1 1 0 0 0

Both of those have size 2, and they belong to the same beat. So there is exactly 1 beat of size 2

  • Classification of the beats of size 3

Let B be a bit of size 2.

  1. First we will show that we can find a record in B of the form (x, y, z, x, z, y) where x, y, z are not all equal

f a record in B. We have |Stab(f)| = 2 so Stab(f) = {e, a} or {e, ap} or {e, ap2}.

Let’s assume Stab(f) = {e, a}. Then a.f = f. If we have also p.f = f Then B has size 1 which is absurd. So we have \(p.f \neq f\) and \(\phi(p)\) has order 3 which means B = {f, pf, p2.f}

a.f = f implies (f(4), f(6), f(5), f(1), f(3), f(2)) = (f(1), f(2), f(3), f(4), f(5), f(6))

So: f(4) = f(1), f(5) = f(3), f(6) = f(2)

Furthermore we can’t have f(1) = f(2) = f(3) otherwise f would be constant and the beat would have size 1.

So the analysis says that f is of the form (x, y, z, x, z, y) where x, y, z are not all equal.

For example (1, 0, 0, 1, 0, 0) or (0, 1, 0, 0, 0, 0, 1) or (1, 1, 0, 1, 0, 1)

  1. Here we will show that a function of the above indeed spans a beat of size 2

Let’s assume that f is of this form. Then clearly \(p.f \neq f\) and \(a.f = f\) so Stab(f) = {e, a}. So the beat of f has size 3.

  1. Here we will show that 2 different function of the above form cannot share the same beat

Let g be another function of this form (x’, y’, z’, x’, z’, y’) and suppose g is in O(f). Then g = pf or g = pf2. Let’s assume g = pf. Then g = (z, x, y, y, x, z)

So we can deduce z = y: f = (x, y, y, x, y, y) and g = (y, x, y, y, x, y) Furthermore we still have a.g = g so in particular g(5) = g(3) which means x = y. So in the end x = y = z which is absurd. So that means g is not in O(f).

  1. Conclusion

Total number of beats is the total number of triplets (x, y, z) minus the 2 constant triplets \(2*2*2 - 2 = 6\). So there are 6 beats of size 2. They are:

1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 0
0 1 1 0 1 1
1 0 1 1 1 0
1 1 0 1 0 1

  • Beats of size 6.

Let n be the number of 6 beats. We have \(64 = 2 + 1*2 + 6*3 + n*6\) so n = 7. We can see that the function \(card : f \mapsto \sum_{1 \leq i \leq 6} f(i)\) is a beat invariant. \(\forall g \in S3, f \in Rec, card(g \cdot f) = card(f)\) So we can classify the beats of size 6 by their cardinal.

  1. If a beat has cardinal 0 then it is constant So it cannot be of size 6

  2. If a beat has cardinal 1 Let B be a beat of cardinal size 1. Let f be a recording in B. There is a unique index i that gives the place of the unique 1 in f. We can find an element that acts on f that maps i to 1. For example if i = 4, a will do, if i = 5, ap will do… So we can assume f to be 1 0 0 0 0 0. We can check that the beat of f is of size 6. So there is only 1 beat of cardinal 1 of size 6.

  3. If a beat has cardinal 2 Similar to the previous cardinal. We can always find a beat representent which starts with a 1. That means that there are at most 5 beats: 1 1 0 0 0 0
    1 0 1 0 0 0 = p . 1 1 0 0 0 0 1 0 0 1 0 0 Orbit has size 3 (a is in stabilizer)
    1 0 0 0 1 0 Orbit has size 3 (ap is in stabilizer)
    1 0 0 0 0 1 Orbit has size 3 (ap2 is in stabilizer)

all(apprec(gp)(1, 1, 0, 0, 0, 0) == c(1, 0, 1, 0, 0, 0))
## [1] TRUE

So there is only 1 possible beat of cardinal 2 and size 6. which is: 1 1 0 0 0 0, 0 1 1 0 0 0, 1 0 1 0 0 0, 0 0 0 1 0 1, 0 0 0 0 1 1, 0 0 0 1 1 0

  1. If a beat has cardinal 3 Let f be a recording. We can choose it such that it starts with a 1. So we have 10 possibilities 1 1 1 0 0 0 Orbit has size 2
    1 1 0 1 0 0
    1 1 0 0 1 0
    1 1 0 0 0 1 1 0 1 1 0 0 = p2 . 1 1 0 0 1 0
    1 0 1 0 1 0 = p2 . 1 1 0 0 0 1
    1 0 1 0 0 1 = p2 . 1 1 0 1 0 0 1 0 0 1 1 0 = ap . 1 1 0 0 1 0 1 0 0 1 0 1 = a . 1 1 0 1 0 0
    1 0 0 0 1 1 = ap2 . 1 1 0 0 0 1
all(apprec(gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 1, 1, 0, 0),
    apprec(gp)(1, 1, 0, 0, 0, 1) == c(1, 0, 1, 0, 1, 0),
    apprec(gp)(1, 1, 0, 1, 0, 0) == c(1, 0, 1, 0, 0, 1),
    apprec(ga*gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 0, 1, 1, 0),
    apprec(ga)(1, 1, 0, 1, 0, 0) == c(1, 0, 0, 1, 0, 1),
    apprec(ga*gp^2)(1, 1, 0, 0, 0, 1) == c(1, 0, 0, 0, 1, 1))
## [1] TRUE

So we have at most 3 beats of cardinal 3 and size 6. We verify that each of those 3 recording span distinct beats and that they each have size 6

  1. If a beat has cardinal 4

Let B be a beat of cardinal 4, we verify that \(\eta(B)\) is a beat of cardinal 2. Since \(\eta\) is a bijection preserving beats we know that it gives a correspondance between beats of cardinal 2 and beats of cardinal 4. So there is only one beat of cardinal 4. And it is given by: 0 0 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1 1 1 1 0 1 0 <- I like this one
1 1 1 1 0 0
1 1 1 0 0 1

  • Conclusion
Beat size Number
1 2
2 1
3 6
6 7

Other actions

  • The action of S3 on S3/<p> is not faithfull. S3/<p> = {{e, p, p2}, {a, b, c}} Any element of <p> is sent to the identity. Any other element is sent to ({e, p, p2} {a, b, c})

  • There is also an action of S3 on {a, b, c}.

  • And an action of S3 on <p>

All the transitive, faithfull actions of S3

Let \(\phi\) be a transitive, faithfull set action \(S3 \rightarrow S(\mathcal{A})\). Where \(\mathcal{A}\) is any set. We note: \(g \bullet x = \phi(g)(x)\) for \(g \in S3, a \in \mathcal{A}\)

First we would like to show that \(\mathcal{A}\) has 6 elements.

Let \(a_0 \in \mathcal{A}\), we let \(f_{a_0}: S3 \rightarrow \mathcal{A}\) defined by \(f_{a_0}(g) = g \bullet a_0\)

Since the action is transitive \(f_{a_0}\) is surjective. Let’s \(g_1, g_2 \in \mathrm{S3}\). \[f_{a_0}(g_1) = f_{a_0}(g_2) \iff g_1 \bullet a_0 = g_2 \bullet a_0 \iff g_1 g_2^{-1} \bullet a_0 = a_0\]

How to see if 2 actions are isomorphic?

In all this file G is a finite group and S is a set.

An action is a group morphism \(\phi_1: G \rightarrow Aut(S)\) where S is some set. Let \(\phi_2: G \rightarrow Aut(S2)\) be another group action. 2 action are isomorphic iff there exist a set isomorphism \(f: S \rightarrow S2\) such that \[\forall g \in G, f(\phi_1(g)(x)) = \phi_2(g)(f(x))\]

The next property shows that if we have verified the property on f for \(g_1, g_2 \in G\), then the property holds for \(g_1g_2\). \[f(\phi_1(g_1g_2)(x)) = f(\phi_1(g_1)(\phi_1(g_2)(x))) = \phi_2(g_1)(f(\phi_1(g_2)x)) = \phi_2(g_1)(\phi_2(g_2)(fx)) = \phi_2(g_1g_2)(fx)\]

That means that we only need to verify the property on a set of generators for G.

Example

Let’s show that the action on {1, 2, 3} is isomorphic to the action on {{1, 2}, {1, 3}, {2, 3}} by taking f: 1 -> {2, 3} f: 2 -> {1, 3} f: 3 -> {1, 2}

f(p.1) = f(2) = {1, 3} p.f(1) = p.{2, 3} = {1, 3}

f(p.2) = f(3) = {1, 2} p.f(2) = p.{1, 3} = {1, 2}

f(a.1) = f(2) = {1, 3} a.f(1) = a.{2, 3} = {1, 3}

f(a.3) = f(3) = a.f(3) => f(3) = {1, 2}

f(b.2) = f(2) = b.f(2) => f(2) = {1, 3}

f(c.1) = f(1) = c.f(1) => f(1) = {2, 3}

So f is an isomorphism of actions.

Automorphism group of S3

Inner automorphisms

Conjugation by an element creates an automorphism. The conjugation by p has the following effect:

## a^p: (2,3)
## b^p: (1,2)
## c^p: (1,3)
## p^p: (1,2,3)
## p2^p: (1,3,2)

So conj(p) = (a c b)

Here is the conjugation by p2:

## a^p2: (1,3)
## b^p2: (2,3)
## c^p2: (1,2)
## p^p2: (1,2,3)
## p2^p2: (1,3,2)

So conj(p2) = (a b c)

Here is the conjugation by a:

## a^a: (1,2)
## b^a: (2,3)
## c^a: (1,3)
## p^a: (1,3,2)
## p2^a: (1,2,3)

So conj(a) = (b c) (p p2)

Here is the conjugation by b:

## a^b: (2,3)
## b^b: (1,3)
## c^b: (1,2)
## p^b: (1,3,2)
## p2^b: (1,2,3)

So conj(b) = (a c) (p p2)

Here is the conjugation by c:

## a^c: (1,3)
## b^c: (1,2)
## c^c: (2,3)
## p^c: (1,3,2)
## p2^c: (1,2,3)

So conj(c) = (a b)(p p2)

So together with the identity there are 6 inner automorphisms.

Structure of the automorphism group

We will show that Inner(S3) = S3 conj(a)^2 = e conj(p)^3 = e conj(p)^conj(a) = conj a-1 o conj p o conj a = conj a-1pa = conj p2 = conj(p)^2

Since the generators of Inner(S3) have the same relations as those of S3 we know the 2 groups are isomorphic.

Total group or isomorphism

We can show that there are no outer isomorphism. Indeed an automorphism maps elements to elements of the same order. There are thus 2 possibilities for mapping p and 3 possibilities for mapping a. Since a and p generate S3 this 2 images will define uniquely a mapping. There are at most 3*2 automorphisms and according to the previous paragraphs we already have 6 inner automorphisms. So all the automorphism are inner.

Matrix representation of an automorphism

Since an automorphism is uniquely defined by its image of the generators a and p we might be able to write them as a matrix. Indeed the reason we are able to write linear operators as matrix is because they are defined by their action on a basis which is a generator set of the whole vector space.

First lets try to write elements of S3 as vectors: we note a = (1, 0) and p = (0, 1) (0, x) * (1, m) = p^x * a * p^m = a * a p^x * a p^m = (1, 2*x+m)

(g1, n1) * (g2, n2) = g1n1g2n2 = g1g2inv(g2)n1g2n2 = g1g2n1^g2n2 = (g1g2, n1^g2*n2)

inv(g1) * (g2, n2) * g1 = inv(g1) * (g2*g1, n2^g1) = (g2^g1, n2^g1) conj(g1) = g1 e e g1